package com.sheng.leetcode.year2023.month03.day20;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/03/20
 * <p>
 * 1012. 至少有 1 位重复的数字<p>
 * <p>
 * 给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 20<p>
 * 输出：1<p>
 * 解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 100<p>
 * 输出：10<p>
 * 解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。<p>
 * <p>
 * 示例 3：<p>
 * 输入：n = 1000<p>
 * 输出：262<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= 10^9<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/numbers-with-repeated-digits">1012. 至少有 1 位重复的数字</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1012 {

    @Test
    public void test01() {
        int n = 20;
//        int n = 100;
//        int n = 1000;
        System.out.println(new Solution().numDupDigitsAtMostN(n));
    }
}

class Solution {
    private int[] nums = new int[11];
    private Integer[][] dp = new Integer[11][1 << 11];

    public int numDupDigitsAtMostN(int n) {
        // 获取 1 - n 范围内包含有至少一个重复数字的正整数的个数
        // 从二位数开始，每多一位，可重复的数组的数量就上升一位
        return n - f(n);
    }

    private int f(int n) {
        int i = -1;
        for (; n > 0; n /= 10) {
            nums[++i] = n % 10;
        }
        return dfs(i, 0, true, true);
    }

    private int dfs(int pos, int mask, boolean lead, boolean limit) {
        if (pos < 0) {
            return lead ? 0 : 1;
        }
        if (!lead && !limit && dp[pos][mask] != null) {
            return dp[pos][mask];
        }
        int ans = 0;
        int up = limit ? nums[pos] : 9;
        for (int i = 0; i <= up; ++i) {
            if ((mask >> i & 1) == 1) {
                continue;
            }
            if (i == 0 && lead) {
                ans += dfs(pos - 1, mask, lead, limit && i == up);
            } else {
                ans += dfs(pos - 1, mask | 1 << i, false, limit && i == up);
            }
        }
        if (!lead && !limit) {
            dp[pos][mask] = ans;
        }
        return ans;
    }
}
